Compilers are generally used to transform one representation of a computer program procedure into another representation. Typically, but not exclusively, compilers are used to transform a human readable form of a program such as source code into a machine readable form such as object code.
One type of compiler is an optimizing compiler which includes an optimizer or optimizing module for enhancing the performance of the machine readable representation of a program. Some optimizing compilers are separate from a primary compiler, while others are built into a primary compiler to form a multi-pass compiler. Both types of compilers may operate either on a human readable form, a machine readable form, or any intermediate representation between these forms.
Many optimizing modules of compilers operate on intermediate representations of computer programs or procedures. Typically a program or procedure being translated is broken down into a series of “statements”, each of which contains zero or more “operands” or “data items”. A data item may be “defined”, meaning that it is given a value by the statement, or “used”, meaning that its value is fed into the computation represented by the statement. For example, the statement “x=y+z” defines x and uses y and z. Optimization of a program often involves locating individual statements or groups of statements which can be eliminated or rewritten in such a way as to reduce the total number of statements in the program or in a particular flow path through the program. For example, a complicated expression might be computed at two distant points within the same procedure. If the variables used in the expression are not modified to contain different values between the first and second computations, the value can be computed only once, at the first point in the procedure, and saved in a temporary location for use at the second point in the procedure, thus avoiding recomputation at the second point. This particular form of optimization is known as “common (sub)expression elimination”.
The main problem in optimizing a procedure is to determine at which points of the procedure various kinds of information are available. For example, to perform common (sub)expression elimination, it is necessary to know at which points the variables used by the procedure are modified. To determine such facts, a dataflow analysis is performed on the program.
To perform dataflow analysis, possible paths of execution through a procedure may be represented by a control flow graph (CFG). Statements may be grouped together into basic blocks, which are maximal sequences of straight-line code. In other words, there is no way to branch into or out of a basic block except at the beginning or end. A CFG is a graph with one node for each basic block in the procedure. The CFG includes an arc from block A to block B if it is possible for block B to be executed immediately after block A has been executed. In such a case, B is called a “successor” of A, and A is called a “predecessor” of B.
The CFG is generated by a forward pass through the procedure to identify basic blocks and transitions between basic blocks, and form an ordered representation of those blocks and the branches between blocks. One well-known approach for ordering the blocks in the CFG is to form a “depth first” ordering of the basic blocks of the program. This approach is described in Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, copyright 1986, reprinted 1988, which is incorporated by reference herein, particularly in sections 10.6 and 10.9. In a depth first ordering, each basic block is assigned a “dfo” number, with the following property: if every path from the start of the program to block Y must pass through block X, then the dfo number for X is less than the dfo number for Y, which is written ddfo(X)<dfo(Y).
After generating a CFG, optimization typically involves computing various properties at points of interest in the procedure, for example, the properties of the statements in each block in the CFG. Often, a matrix of binary values (bits) such as is shown in FIG. 1, is used to identify these properties. In a typical approach, there are several rows 10 in the matrix for each block in the program, each row 10 representing one property of the statements in the block. There is one column 12 in the matrix for each property of interest during optimization. At each row and column location, there is a bit which has either a “1” or a “0” value.
For example, in the matrix shown in FIG. 1, each block B is associated with four rows 10, a row in[B] for identifying expressions that are available upon entry to block B, a row out[B] for identifying expressions that are available upon exit from block B, a row gen[B] for identifying expressions that are generated by statements in block B, and a row kill[B] for identifying expressions whose constituent variables are modified by statements in block B. The columns 12 in the matrix relate to particular expressions, numbered 1, 2, 3 etc. Thus, the “1” located in the row for in[B2] and the column for expression 6, indicates that expression 6 is available upon entry to block B2; the “0” located in the row for in[B1] and the column for expression 2, indicates that expression 2 is not available upon entry to block B1.
A difficulty that arises with the representation shown in FIG. 1, is that in practice, most of the bits in the matrix are zero (i.e., the matrix is “sparse”). In a typical case where the bits in the matrix relate to the status of particular expressions, the matrix is typically sparse because, normally, specific expressions are only used or useful in a small portion of a procedure. A large, sparse bit matrix not only consumes large quantities of space, but also requires a large amount of time to repeatedly scan in the manner needed for complex dataflow analysis.